/* File: maze_4a.c
 * --------------------
 * Author: Albin Olausson & Stella Wallin
 * Last modified: 2014-04-17
 * Task: A program that find the 
 * shortest path out from a maze.
 */

#include <stdio.h>
#include "genlib.h"
#include "graphics.h"
#include "mazelib.h"
#include "simpio.h"

/* Constants*/ 

#define NoSolution 10000

/* Private function prototypes */
static pointT AdjacentPoint(pointT pt, directionT dir);

/* Prototypes */
int shortestPathLength(pointT pt);


/* Main program */

main(){
    string MazeFile;
    int shortestPath;

    printf("Program by S. Wallin & A. Olausson.\n\n");
    printf("Please enter the name of the mazefile: ");
    MazeFile = GetLine();
    InitGraphics();
    ReadMazeMap(MazeFile);
    shortestPath = shortestPathLength(GetStartPosition()); 
    
	if (shortestPath == NoSolution+1)
		printf("No solution was found");
	else 
		printf("The shortest path was %d.\n", shortestPath-1);
}

/*
 * Function: AdjacentPoint
 * Usage: newpt = AdjacentPoint(pt, dir);
 * --------------------------------------
 * This function returns the pointT that results from moving
 * one square from pt in the direction specified by dir.  For
 * example, if pt is the point (1,1), AdjacentPoint(pt, East)
 * would return the point (2,1).
 */

static pointT AdjacentPoint(pointT pt, directionT dir)
{
    pointT newpt;
    
    newpt = pt;
    switch (dir) {
      case North: newpt.y++; break;
      case East:  newpt.x++; break;
      case South: newpt.y--; break;
      case West:  newpt.x--; break;;
    }
    return (newpt);
}

/*
 * Function: shortestPathLength
 * Usage: shortestPath = shortestPathLength(pt);
 * ----------------------
 * A recursive function that compares
 * all paths that leads to an exit and
 * returns the shortest one.
 */

int shortestPathLength(pointT pt){
	int len, shortestPath;
        
	if (OutsideMaze(pt))
		return TRUE;       

	if (IsMarked(pt))
		return NoSolution;

	shortestPath = NoSolution;
    MarkSquare(pt);
       
    if (!WallExists(pt, North)){
        len = shortestPathLength(AdjacentPoint(pt, North)); 
		if (len < shortestPath)
			shortestPath = len;
	}
	if (!WallExists(pt, East)){
		len = shortestPathLength(AdjacentPoint(pt, East)); 
		if (len < shortestPath)
			shortestPath = len;
	}
	if (!WallExists(pt, South)){
		len = shortestPathLength(AdjacentPoint(pt, South)); 
		if (len < shortestPath)
			shortestPath = len;
	}
	if (!WallExists(pt, West)){
		len = shortestPathLength(AdjacentPoint(pt, West)); 
		if (len < shortestPath)
			shortestPath = len;
	}

	UnmarkSquare(pt);
	return (shortestPath+1);
}